package net.tp.algo.rmq;

/**
 *
 * <p>Sparse Table.</p>
 *
 * <p>Sparse table is used to make range minimum query (RMQ) in $O(1)$ time. It takes $O(n log(n))$ time and space to
 * pre-process the table. The sparse table concept is used in ±1 RMQ where the pre-processing takes $O(n)$ time and space
 * and the query time is $O(1)$.</p>
 *
 * <p>$M(i,j)$ is the index of the minimum value in the range $[i,i+2^j)$ ⇒ $M(i,0) = i$.
 * $V(i,j)$ is the the minimum value in the range $[i,i+2^j)$. $V$ is not needed in the algorithm because $V(i,j) = a[M(i,j)]$.</p>
 *
 * <pre>
 *
 *          i: 0   1   2   3   4   5   6   7   8   9
 *          a: 2   4   3   5   6   1   8   9   1   7
 * M(1,0) = 1:    └─┘
 * M(1,1) = 2:    └─────┘
 * M(1,2) = 2:    └─────────────┘
 * M(1,3) = 5:    └─────────────────────────────┘
 *
 * M(1,2) = 2:    └─────────────┘
 * M(3,2) = 5:            └─────────────┘
 * </pre>
 * {@code rmq(1,6) = M(3,2) = 5 because V(3,2) < V(1,2) }
 *
 * <p>To populate, use dynamic programming:
 * $$\table M(i,0) ,=, i; M(i,j) ,=, \text"index of " min \{ V(i,j-1), V(i+2^(j-1), j-1) \}, 0 &lt; j ≤ log(n)+1$$
 * </p>
 *
 * <pre>
 *          i: 0   1   2   3   4   5   6   7   8   9
 *          a: 2   4   3   5   6   1   8   9   1   7
 * M(1,2) = 2:    └─────────────┘
 * M(5,2) = 5:                    └─────────────┘
 * M(1,3) = 5:    └─────────────────────────────┘
 *
 * </pre>
 *
 *
 * @author Trung Phan
 *
 * @time $O(n log(n))$ processing time, $O(1)$ query time.
 * @space $O(n log(n))$
 *
 */
public class SparseTable {

    private int[] a;
    private int l;

    private int M[][];

    public SparseTable(int[] a) {
        int n = a.length;

        this.a = a;
        this.l = (int)(Math.log(n) / Math.log(2)) + 1;

        M = new int[n][l];
        for (int i = 0; i < n; i++) {
            M[i][0] = i;
        }

        for (int j = 1, d = 1; j < l; j++, d *= 2) { // d = 2^j / 2
            for (int i = 0; i < n; i++) {
                if (i+d >= n || a[M[i][j-1]] <= a[M[i+d][j-1]]) {
                    M[i][j] = M[i][j-1];
                }
                else {
                    M[i][j] = M[i+d][j-1];
                }
            }
        }
    }

    public int minIndex(int lo, int hi) {
        if (hi < lo) throw new IllegalArgumentException();
        if (lo < 0 || lo >= M.length || hi < 0 || hi >= M.length) throw new IndexOutOfBoundsException();

        int d = (int)(Math.log(hi+1-lo) / Math.log(2));
        if (a[M[lo][d]] <= a[M[hi+1-(1<<d) ][d]]) {
            return M[lo][d];
        }
        else {
            return M[hi-1][d];
        }
    }

}
